package ar.edu.itba.tp1.gps;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import ar.edu.itba.tp1.gps.api.GPSProblem;
import ar.edu.itba.tp1.gps.api.GPSRule;
import ar.edu.itba.tp1.gps.api.GPSState;
import ar.edu.itba.tp1.gps.exception.NotAppliableException;

public abstract class GPSEngine {

	protected List<GPSNode> open = new LinkedList<GPSNode>();

//	protected List<GPSNode> closed = new ArrayList<GPSNode>();
	
	// --
	private static Map<GPSState, List<GPSNode>> openHash = new HashMap<GPSState, List<GPSNode>>();
    private static Map<GPSState, List<GPSNode>> closeHash = new HashMap<GPSState, List<GPSNode>>();
    // --

	private GPSProblem problem;
	private Integer maxLevelNode;

	// Use this variable in the addNode implementation
	protected SearchStrategy strategy;
	
	private Integer numberOfStates;

	public void engine(GPSProblem myProblem, SearchStrategy myStrategy) {

		problem = myProblem;
		strategy = myStrategy;
		Integer currentTreeLevel = 1;
		boolean finished = false;
		boolean failed = false;
		numberOfStates = 0;
		long explosionCounter = 0;

		do {
			failed = false;
			GPSNode rootNode = new GPSNode(problem.getInitState(), 0);
			rootNode.setNodeLevel(0);
			maxLevelNode = 0;
	
			open.add(rootNode);
			
			//--
	        List<GPSNode> ol = new LinkedList<GPSNode>();
	        openHash.put(rootNode.getState(), ol);
	        ol.add(rootNode);
	        //--
			while (!failed && !finished) {
				if (open.size() <= 0) {
					failed = true;
				} else {
					GPSNode currentNode = open.get(0);
	//				closed.add(currentNode);
					
					//--
	                List<GPSNode> closeList = closeHash.get(currentNode.getState());
	                if(closeList == null){
	                        closeList = new LinkedList<GPSNode>();
	                        closeHash.put(currentNode.getState(), closeList);
	                }
	                closeList.add(currentNode);
	                openHash.get(currentNode.getState()).remove(currentNode);
	                //--
					
					open.remove(0);
					if (isGoal(currentNode)) {
						finished = true;
						System.out.println(currentNode.getSolution());
						System.out.println("Expanded nodes: " + explosionCounter);
						System.out.println("Open nodes: " + open.size());
						System.out.println("States generated: " + numberOfStates);
					} else {
						if (strategy != SearchStrategy.PI || currentNode.getNodeLevel() < currentTreeLevel) {
							explosionCounter++;
							System.out.println("Node: " + currentNode.toString());
							explode(currentNode);
						}
					}
				}
			}
			open = new LinkedList<GPSNode>();
			openHash = new HashMap<GPSState, List<GPSNode>>();
			closeHash = new HashMap<GPSState, List<GPSNode>>();
		} while (strategy == SearchStrategy.PI && !finished && maxLevelNode == currentTreeLevel++);//currentTreeLevel < (GPSRun.n*GPSRun.n)+1);

		if (strategy == SearchStrategy.PI && !finished) {
			failed = true;
		}
		
		if (finished) {
			System.out.println("OK! solution found!");
		} else if (failed) {
			System.err.println("FAILED! solution not found!");
		}
	}

	private  boolean isGoal(GPSNode currentNode) {
		return currentNode.getState() != null
				&& currentNode.getState().isGoalState();//compare(problem.getGoalState());
	}

	private  boolean explode(GPSNode node) {
		if(problem.getRules() == null){
			System.err.println("No rules!");
			return false;
		}
		
		for (GPSRule rule : problem.getRules()) {
			GPSState newState = null;
			try {
				newState = rule.evalRule(node.getState());
			} catch (NotAppliableException e) {
				// Do nothing
			}
			if (newState != null
					//&& !checkBranch(node, newState)
					&& !checkOpenAndClosed(node.getCost() + rule.getCost(),
							newState)) {
				GPSNode newNode = new GPSNode(newState, node.getCost()
						+ rule.getCost());
				newNode.setParent(node);
				newNode.setNodeLevel(node.getNodeLevel()+1);
				maxLevelNode = Math.max(maxLevelNode, node.getNodeLevel()+1);
				addNode(newNode);
				
				List<GPSNode> openList = openHash.get(newNode.getState());
                if(openList == null){
                        openList = new LinkedList<GPSNode>();
                        numberOfStates++;
                        openHash.put(newNode.getState(), openList);
                }
                openList.add(newNode);
				
			}
		}
		return true;
	}

	private  boolean checkOpenAndClosed(Integer cost, GPSState state) {
		List<GPSNode> openNodes = openHash.get(state);
        if(openNodes != null){
                for(GPSNode n: openNodes){
                        if(n != null && n.getCost() < cost)
                                return true;
                }
        }
        
        List<GPSNode> closeNodes = closeHash.get(state);
        if(closeNodes != null){
                for(GPSNode n: closeNodes){
                        if(n != null && n.getCost() < cost)
                                return true;
                }
        }
        
        return false;
	}

	public abstract void addNode(GPSNode node);
	
}
